package com.demo.java.OD401_450.OD435;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【图像物体的边界(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146323866
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入矩阵的维度
        int m = sc.nextInt();
        int n = sc.nextInt();

        String[][] mat = new String[m][n];  // 创建矩阵
        // 输入矩阵元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = sc.next();  // 将每个元素存储在矩阵中
            }
        }

        // 识别所有的图像区域
        Set<Set<Integer>> spotAggs = identifySpots(m, n, mat);

        // 合并相邻的图像区域
        consolidateAdjacentSpots(m, n, mat, spotAggs);

        // 输出图像区域的数量
        System.out.println(spotAggs.size());
    }

    // 识别矩阵中的图像区域
    private static Set<Set<Integer>> identifySpots(int m, int n, String[][] mat) {
        Set<Set<Integer>> spotAggs = new HashSet<>();

        // 遍历矩阵中的每个像素
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                // 如果当前像素是“5”，则认为是一个新的图像区域的起始
                if ("5".equals(mat[x][y])) {
                    Set<Integer> spot = new HashSet<>();
                    spot.add(x * n + y);  // 将当前“5”像素添加到该图像区域
                    spotAggs.add(spot);  // 将图像区域添加到集合中
                }
            }
        }

        return spotAggs;
    }

    // 合并相邻的图像区域
    private static void consolidateAdjacentSpots(int m, int n, String[][] mat, Set<Set<Integer>> spotAggs) {
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                // 只有当前像素是“5”时才考虑合并相邻区域
                if ("5".equals(mat[x][y])) {
                    final int currX = x;
                    final int currY = y;

                    ArrayList<Set<Integer>> adjAggs = new ArrayList<>();
                    // 查找相邻的图像区域
                    for (Set<Integer> agg : spotAggs) {
                        if (agg.stream().anyMatch(spot -> isAdjacent(spot, currX, currY, n))) {
                            adjAggs.add(agg);  // 将相邻的区域加入到临时列表中
                        }
                    }

                    // 更新图像区域
                    updateSpotAggs(spotAggs, x, y, adjAggs);
                }
            }
        }
    }

    // 更新图像区域合并
    private static void updateSpotAggs(Set<Set<Integer>> spotAggs, int x, int y, ArrayList<Set<Integer>> adjAggs) {
        if (adjAggs.size() == 1) {
            adjAggs.get(0).add(x * y);  // 只有一个相邻区域时直接加入
        } else if (adjAggs.size() > 1) {
            Set<Integer> newAgg = new HashSet<>();
            newAgg.add(x * y);
            // 合并多个相邻区域
            for (Set<Integer> i : adjAggs) {
                newAgg.addAll(i);
                spotAggs.remove(i);  // 删除已合并的区域
            }
            spotAggs.add(newAgg);  // 将新的合并区域添加到集合中
        } else {
            Set<Integer> newAgg = new HashSet<>();
            newAgg.add(x * y);
            spotAggs.add(newAgg);  // 如果没有相邻区域，则创建新区域
        }
    }

    // 判断两个位置是否相邻
    private static boolean isAdjacent(int spot, int x, int y, int n) {
        int spotX = spot / n;
        int spotY = spot % n;
        return Math.abs(spotX - x) <= 3 && Math.abs(spotY - y) <= 3;  // 通过坐标差值判断是否相邻
    }

}
